題目連結: Same Tree

題目描述為給定兩個二元樹，要判定它們是否相等。

思路 1: 遍歷法

我們可以從兩個 tree 的 root: p,q 開始檢查是否相等，再往下比較 p,q 的左節點與右節點是否均相等。只要有一處不相等即返回 flase，若全部節點均相等則返回 true。

• 複雜度評估
  設給定兩樹的節點數量為 M,N。至多需要遍歷全部節點一次，時間複雜度為 O(M+N)。此方法只用了常數個變數，與 M,N 無關，空間複雜度為 O(1)。

參考程式碼

func isSameTree(p *TreeNode, q *TreeNode) bool {
    
    if  p==nil &&q==nil{
        return true
    }
    
    if p==nil || q==nil{
        return false
    }
    
    if p.Val!=q.Val{
        return false
    }
    
    
    return isSameTree(p.Left ,q.Left) &&  isSameTree(p.Right, q.Right)
    
}

小結:

方法 1 用遞迴方式實現了二元樹的遍歷。wiki 二元樹的遍歷條目有詳細介紹各種遍歷方式，均有其應用情境。此外，二元樹的結構讓我們對其存放元素能進行高效的搜尋，資料庫即採用此設計。有關二元樹的其他應用，可參考此篇問答: What are the applications of binary trees?
我將解法上傳程式碼到此，因此題需要實作 TreeNode，我尚未加上測試過程。